package com.sx.sx1.lintcode.day717;

public class LC3810 {

    static class Solution {
        /**
         * @param s: A binary string
         * @return: minimum number of operands required
         */
        public int reverseBinaryString(String s) {
            /*
            方法：双指针
            我们要将给定的二进制字符串 s 进行反转，这意味着最终目标字符串是 s 的逆序字符串，可以用两个指针来实现匹配过程：

            指针 left 从原字符串 s 的开始遍历
            指针 right 从逆序字符串 temp 开始遍历
            需要注意的是：这里的 left 和 right 并不是处于同一个字符串上的两个指针，而是分别位于两个字符串的指针，比较逻辑如下：

            比较 s[left] 和 temp[right] 的字符
            如果 s[left] == temp[right]，则两个指针同时向前移动，表示这个字符已经在正确的位置上，不需要进行操作
            否则，仅移动 left 指针，同时操作数 res 自增 1，表示这个字符需要移动到末尾

             */
            String rs = new StringBuilder(s).reverse().toString();
            int res =0;
            int left=0;
            int right =0;
            while (left< s.length()){
                if(s.charAt(left)!= rs.charAt(right)){
                    left++;
                    res++;
                }else{
                    left++;
                    right++;
                }
            }
            return res;
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.reverseBinaryString("00110101"));
        System.out.println(obj.reverseBinaryString("010101"));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
3810 · 反转二进制字符串
算法
简单
通过率
65%

题目
题解3
笔记
讨论
排名
记录
描述
给定一个二进制字符串 s，找到将其反转所需的最小操作数，其中操作的定义如下：

从 任意索引 处移除一个字符，并将这个字符添加到字符串的末尾
最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


1
≤
𝑠
.
𝑙
𝑒
𝑛
𝑔
𝑡
ℎ
≤
1
0
5
1≤s.length≤10
5

样例
样例 1：

输入：
s = "00110101"
输出：
3
解释：
以下是其中一种可行的操作：
"00110101" -> "00101011"，将索引为 3 的字符移动到末尾
"00101011" -> "01010110"，将索引为 0 的字符移动到末尾
"01010110" -> "10101100"，将索引为 0 的字符移动到末尾
样例 2：

输入：
s = "010101"
输出：
1
解释：
"010101" -> "101010"，将索引为 0 的字符移动到末尾
标签
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
15 分 00 秒
123456789
public class Solution {
    /**
     * @param s: A binary string
     * @return: minimum number of operands required

public int reverseBinaryString(String s) {
    // write your code here
}
}
控制台
        历史提交




解题思路
方法：双指针
我们要将给定的二进制字符串 s 进行反转，这意味着最终目标字符串是 s 的逆序字符串，可以用两个指针来实现匹配过程：

指针 left 从原字符串 s 的开始遍历
指针 right 从逆序字符串 temp 开始遍历
需要注意的是：这里的 left 和 right 并不是处于同一个字符串上的两个指针，而是分别位于两个字符串的指针，比较逻辑如下：

比较 s[left] 和 temp[right] 的字符
如果 s[left] == temp[right]，则两个指针同时向前移动，表示这个字符已经在正确的位置上，不需要进行操作
否则，仅移动 left 指针，同时操作数 res 自增 1，表示这个字符需要移动到末尾

public class Solution {

    public int reverseBinaryString(String s) {
        String temp = new StringBuilder(s).reverse().toString();
        int left = 0, right = 0, res = 0;
        while (left < s.length()) {
            if (s.charAt(left) != temp.charAt(right)) {
                left++;
                res++;
            } else {
                left++;
                right++;
            }
        }
        return res;
    }
}
 */